package com.up.interview.dataStructuresAndAlgorithms.dataS;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author: liuchengjun
 * @title: StackTest
 * @projectName: 海联技术中台V2.0
 * @depart 软件事业部
 * @description:
 * @date: 2025/10/24/周五 13:57 (星期五)
 * @since V2.0
 */
public class StackTest {

    public static void main(String[] args) {
        // 测试用例（字符串数组形式）
        StackTest stackTest = new StackTest();
        String[][] testCases = {
                {"3", "+", "4", "*", "2"},
                {"(", "3", "+", "4", ")", "*", "2"},
                {"10", "+", "2", "*", "6"},
                {"100", "*", "2", "+", "12"},
                {"100", "*", "(", "2", "+", "12", ")"},
                {"9", "+", "(", "3", "-", "1", ")", "*", "3", "+", "10", "/", "2"},
                {"3", "+", "4", "*", "2", "/", "(", "1", "-", "5", ")"}
        };
        for (String[] infix : testCases) {
            List<String> strings = stackTest.midToAfter(infix);
            System.out.println(strings);
            Integer i = stackTest.calculateAfter(strings);
            System.out.println("结果:"+i);
        }
    }
    /**
     * 中缀表达式转为后缀
     * 优先级（）>* />+-
     *
     *
     */
    public List<String> midToAfter(String[] s){
        Stack<String> stack = new Stack();
        List<String> res = new ArrayList<>();
        for (int i = 0; i < s.length; i++){
            String data = s[i];
            //1.数字直接输出
            if(isNumber(data)){
                res.add(data);
            } else if (data == "(") {
                //2.符号 ( 入栈
                stack.push(data);
            } else if (data == ")") {
                //3.符号)出栈  直到(
                while(!stack.peek().equals("(")){
                    res.add(stack.pop());
                }
                stack.pop();
            }else {
                //4.其他符号  优先级比较：优先级>栈顶  先运算故入栈  优先级<栈顶  后运算故出栈直到栈为空或栈顶为(
                if(stack.isEmpty()){
                    stack.push(data);
                }else {
                    if(getPrecedence(data) > getPrecedence(stack.peek())){
                        stack.push(data);
                    }else {
                        while(!stack.isEmpty()  && !stack.peek().equals("(")){
                            res.add(stack.pop());
                        }
                        stack.push(data);
                    }
                }
            }
        }
        //while循环  结束条件(相反则条件)
        while (!stack.isEmpty()){
            res.add(stack.pop());
        }
        return res;
    }

    /**
     * 判断运算符的优先级
     * @param operator 运算符
     * @return 优先级数值，数值越大优先级越高
     */
    private  int getPrecedence(String operator) {
        switch (operator) {
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
            default:
                return -1;
        }
    }

    /**
     * 判断是否为运算符
     */
    private  boolean isOperator(String token) {
        return token.equals("+") || token.equals("-") ||
                token.equals("*") || token.equals("/");
    }

    /**
     * 判断是否为数字
     */
    private  boolean isNumber(String token) {
        try {
            Double.parseDouble(token);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }


    public Integer calculateAfter(List<String> res) {
        Stack<Integer> stack = new Stack<>();
        for (String re : res) {
            if(isNumber(re)){
                //1.数字进栈
                stack.push(Integer.parseInt(re));
            }else {
                //2.符号出栈，后操作前，结果入栈
                Integer d1 = stack.pop();
                Integer d2 = stack.pop();
                if(re.equals("+") ){
                    stack.push(d1 + d2);
                }else if(re.equals("*") ){
                    stack.push(d1*d2);
                }else if(re.equals("/") ){
                    stack.push(d2/d1);
                } else if (re.equals("-")) {
                    stack.push(d2-d1);
                }
            }
        }
        return stack.pop();
    }
}
